class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        len_s, len_p, dongtai_list = len(s), len(p), []
        # 初始化填充表格
        for i in range(len_p + 1):
            dongtai_list.append([])
            for j in range(len_s + 1):
                dongtai_list[i].append(False)
        # dongtai_list[i][j]表示s[j-1]和p[i-1]是否匹配
        # 0表示空字符，两个都是空应该匹配
        dongtai_list[0][0] = True
        # 初始化填充，只有当p一直是“字母*”的时候s为空才能匹配
        for i in range(len_p):
            if dongtai_list[i-1][0] and p[i] == "*":
                dongtai_list[i+1][0] = True
        # 开始动态规划，每次更新的格子是dongtai_list[i+1][j+1]
        for i in range(0, len_p):
            for j in range(0, len_s):
                if p[i] == "*":
                    if dongtai_list[i+1][j] and (p[i-1] == s[j] or p[i-1] == ".") or dongtai_list[i-1][j+1]:
                        dongtai_list[i + 1][j + 1] = True
                else:
                    if dongtai_list[i][j] and (p[i] == s[j] or p[i] == "."):
                        dongtai_list[i + 1][j + 1] = True
                # 下面这几句测试用的
                # print(i, j)
        # for lists in dongtai_list:
        #     print(lists)
                # print("-------------")
            # if not flag:
            #     break
        return dongtai_list[len_p][len_s]


a = Solution()
print(a.isMatch("aaa", "ab*ac*a"))
print(a.isMatch("mississippi","mis*is*p*."))
print(a.isMatch("mississippi","mis*is*ip*."))